@PhDThesis{Gomes:2015:DiDiDe,
author = "Gomes, S{\'o}stenes Pereira",
title = "Dispers{\~a}o discreta e decomposi{\c{c}}{\~a}o lagrangeana
desbalanceada para o problema de rotula{\c{c}}{\~a}o
cartogr{\'a}fica de pontos",
school = "Instituto Nacional de Pesquisas Espaciais (INPE)",
year = "2015",
address = "S{\~a}o Jos{\'e} dos Campos",
month = "2015-05-18",
keywords = "problema de rotula{\c{c}}{\~a}o cartogr{\'a}fica de pontos,
otimiza{\c{c}}{\~a}o combinat{\'o}ria, dispers{\~a}o discreta,
point-feature labeling problem, combinatorial optimization,
discrete dispersion.",
abstract = "Este trabalho aborda o Problema de Rotula{\c{c}}{\~a}o
Cartogr{\'a}fica de Pontos (PRCP), que {\'e} um problema de
otimiza{\c{c}}{\~a}o combinat{\'o}ria, demonstrado na
literatura ser NP-dif{\'{\i}}cil. Considera-se que quando todos
os pontos devem ser rotulados e sobreposi{\c{c}}{\~o}es de
r{\'o}tulos s{\~a}o inevit{\'a}veis, o mapa pode ser mais
leg{\'{\i}}vel se os r{\'o}tulos em conflito s{\~a}o
posicionados de maneira dispersiva, isto {\'e}, se os
r{\'o}tulos s{\~a}o posicionados o mais distante
poss{\'{\i}}vel. Neste contexto, {\'e} apresentada uma nova
abordagem para o problema, denominada Dispers{\~a}o Discreta,
j{\'a} utilizada em Problemas de Localiza{\c{c}}{\~a}o de
Facilidades em diversos trabalhos da literatura. Com esta nova
abordagem, o PRCP foi formulado como um Problema de
programa{\c{c}}{\~a}o inteira mista, de maneira a considerar as
dist{\^a}ncias entre posi{\c{c}}{\~o}es candidatas. Um
algoritmo gen{\'e}tico construtivo tamb{\'e}m foi desenvolvido,
para obter resultados em inst{\^a}ncias mais complexas. Por fim,
{\'e} proposta uma Decomposi{\c{c}}{\~a}o Lagrangeana
desbalanceada, que permitiu obter a solu{\c{c}}{\~a}o {\'o}tima
de diversas inst{\^a}ncias do PRCP, al{\'e}m de provar a
otimalidade dos resultados j{\'a} existentes de outras
inst{\^a}ncias. ABSTRACT: This work concerns to the Point-Feature
Cartographic Labeling Problem (PFCLP), which is a NP-Hard
combinatorial problem. It is considered that when all points must
be labeled and overlaps are inevitable, the map can be more
readable if overlapping labels are placed in a dispersive way, i.
e., overlapping labels are distant from each other. Thus, we
present a Discrete Dispersion approach, generally used in the
Facility Location Problem, which considers distance values between
candidate positions. A constructive genetic algorithm to obtain
results in more complex instances is likewise presented. Finally,
we propose an unbalanced Lagrangean Decomposition, which achieved
the optimal solution of several instances of PFCLP, and proved the
optimality of various results of literature.",
committee = "Vijaykumar, Nandamudi Lankalapalli (presidente) and Lorena, Luiz
Antonio Nogueira (orientador) and Ribeiro, Glaydston Mattos
(orientador) and Carvalho, Solon Ven{\^a}ncio de and Becceneri,
Jos{\'e} Carlos and Salles Neto, Luiz Ledu{\'{\i}}no de and
Marins, Fernando Augusto Silva",
copyholder = "SID/SCD",
englishtitle = "Discrete dispersion and unbalanced Lagrangean decomposition for
point-feature cartographic labeling problem",
language = "pt",
pages = "100",
ibi = "8JMKD3MGP3W34P/3JG3TF8",
url = "http://urlib.net/ibi/8JMKD3MGP3W34P/3JG3TF8",
targetfile = "publicacao.pdf",
urlaccessdate = "27 abr. 2024"
}